package sort;

import java.util.Arrays;

public class ShellSort implements MySort {
    public static void main(String[] args) {
        //int a[] = {29,156,88,1,78,35,66};
        //int a[] = {1,2,3,4,5,6,7};
        int a[] = {8,9,1,7,2,3,5,4,6,0};
        //1、3 5 1 6 0 8 9 4 7 2
        //2、0 2 1 4 3 5 7 6 9 8
        //3、0 1 2 3 4 5 6 7 8 9
        ShellSort shellSort = new ShellSort();
        shellSort.sort(a);
        System.out.println(Arrays.toString(a));
    }

    @Override
    public void sort(int[] a) {
        int insertIndex = 0;
        int temp;
        int length = a.length;
        for(int step=length/2;step>0;step/=2){
            for(int i = step;i<length;i++){
                insertIndex = i;
                temp = a[i];
                while(insertIndex>=step&&a[insertIndex-step]>temp){
                    a[insertIndex] = a[insertIndex-step];
                    insertIndex-=step;
                }
                a[insertIndex] = temp;
            }
        }

    }
}
